#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

bool findPath(BinaryTreeNode* root, BinaryTreeNode* node, vector<BinaryTreeNode*> &ret) {
  if (!root)
    return false;
  if (root == node) {
    return true;
  }

  ret.push_back(root);
  bool find = findPath(root->left, node, ret) || findPath(root->right, node, ret);
  if (!find)
    ret.pop_back();
  return find;
}

BinaryTreeNode* findCommonNode(BinaryTreeNode* root,
                               BinaryTreeNode* node1,
                               BinaryTreeNode* node2) {
  vector<BinaryTreeNode*> path1, path2;
  findPath(root, node1, path1);
  findPath(root, node2, path2);

  BinaryTreeNode* common_node = nullptr;
  for (int i = 0; i < path1.size() && i < path2.size(); ++i) {
    if (path1[i]->value == path2[i]->value) {
      common_node = path1[i];
    } else {
      break;
    }
  }

  return common_node;
}

int main() {
  BinaryTreeNode* node1 = CreateBinaryTreeNode(1);
  BinaryTreeNode* node2 = CreateBinaryTreeNode(2);
  BinaryTreeNode* node3 = CreateBinaryTreeNode(3);
  BinaryTreeNode* node4 = CreateBinaryTreeNode(4);
  BinaryTreeNode* node5 = CreateBinaryTreeNode(5);
  BinaryTreeNode* node6 = CreateBinaryTreeNode(6);
  BinaryTreeNode* node7 = CreateBinaryTreeNode(7);
  BinaryTreeNode* node8 = CreateBinaryTreeNode(8);
  BinaryTreeNode* node9 = CreateBinaryTreeNode(9);

  ConnectNode(node1, node2, node3);
  ConnectNode(node2, node4, node5);
  ConnectNode(node4, node6, node7);
  ConnectNode(node5, node8, node9);

  BinaryTreeNode* ret = findCommonNode(node1, node6, node8);
  cout << "The lowest common binary node: " << ret->value << endl;

  return 0;
}
